import codeJamUtils
import operator


def _calculate_optimal_deletions(case):
    numVerticies, adjacencyList = case
    # The key insight here is that only a single node in any full binary tree may serve as the
    # root (the only node with degree 2, as inner nodes have degree 3 and leaves degree 1).
    # It is relatively easy to pair nodes from a rooted tree until it is full and binary.
    return min((_calculate_num_deletions(root, None, adjacencyList)[0] for root in range(numVerticies)))

def _calculate_num_deletions(root, parent, adjacencyList):
    """Computes the number of nodes in the subtree that would need to deleted in the best 
    case in order to make this a full binary tree. Returns the number of deletions and the 
    number of nodes remaining in the resulting full binary tree, as a tuple"""

    adjacentNodes = adjacencyList[root][:]
    if parent is not None:
        adjacentNodes.remove(parent)

    numChildren = len(adjacentNodes)

    if numChildren == 0:
        # No children -> this is already a full binary tree with 1 node. No deletions needed
        return (0, 1)
    elif numChildren == 1:
        # Too bad, we can't add nodes, so we have to delete the entire child's subtree, and
        # we end up with a single node full binary tree
        childDeletions, childSize = _calculate_num_deletions(adjacentNodes[0], root, adjacencyList)
        return (childDeletions + childSize, 1)
    elif numChildren == 2:
        child1Deletions, child1Size = _calculate_num_deletions(adjacentNodes[0], root, adjacencyList)
        child2Deletions, child2Size = _calculate_num_deletions(adjacentNodes[1], root, adjacencyList)
        return (child1Deletions + child2Deletions, child1Size + child2Size + 1)
    else:
        childDeletions = [0 for _ in range(numChildren)]
        childSizes = [0 for _ in range (numChildren)]
        for i in range(numChildren):
            childDeletions[i], childSizes[i] = _calculate_num_deletions(adjacentNodes[i], root, adjacencyList)

        # maximize the size of the subtrees we keep
        iChild = max(enumerate(childSizes), key = operator.itemgetter(1))[0]
        child1Size = childSizes[iChild]
        childSizes[iChild] = 0
        iChild2 = max(enumerate(childSizes), key = operator.itemgetter(1))[0]
        child2Size = childSizes[iChild]
        childSizes[iChild] = 0

        # We zero'd out the sizes in the array for the two children we're keeping
        # The total number of deletions was the number of deletions for each subtree,
        # plus the number of nodes in each subtree that we have to delete to get the 
        # degree of root down to the appropriate number (i.e. must have two children)
        return sum(childDeletions) + sum(childSizes), child1Size + child2Size + 1

def _parse_input(lines):
    numCases = int(lines[0])
    cases = []

    lineNum = 1
    for _ in range(numCases):
        numVerticies = int(lines[lineNum])
        adjacencyList = [[] for _ in range(numVerticies)]

        lineNum += 1
        for _ in range(numVerticies - 1):
            edge = str.split(lines[lineNum])
            node1, node2 = int(edge[0]) - 1, int(edge[1]) - 1
            adjacencyList[node1].append(node2)
            adjacencyList[node2].append(node1)
            lineNum += 1

        cases.append((numVerticies, adjacencyList))
    return cases

if __name__ == "__main__":
    testCases = _parse_input(codeJamUtils.get_input_lines("fullBinaryTree.txt"))
    for i, case in enumerate(testCases):
        output = str(_calculate_optimal_deletions(case))
        codeJamUtils.write_output("fullBinaryTree.txt", i+1, output)


#A tree is a connected graph with no cycles.

#A rooted tree is a tree in which one special vertex is called the root. If there 
#is an edge between X and Y in a rooted tree, we say that Y is a child of X if X is 
#closer to the root than Y (in other words, the shortest path from the root to X is 
#shorter than the shortest path from the root to Y).

#A full binary tree is a rooted tree where every node has either exactly 2 children 
#or 0 children.

#You are given a tree G with N nodes (numbered from 1 to N). You are allowed to 
#delete some of the nodes. When a node is deleted, the edges connected to the 
#deleted node are also deleted. Your task is to delete as few nodes as possible 
#so that the remaining nodes form a full binary tree for some choice of the 
#root from the remaining nodes.

#Input

#The first line of the input gives the number of test cases, T. T test cases follow. 
#The first line of each test case contains a single integer N, the number of nodes in 
#the tree. The following N-1 lines each one will contain two space-separated integers: 
#Xi Yi, indicating that G contains an undirected edge between Xi and Yi.

#Output

#For each test case, output one line containing "Case #x: y", where x is the test 
#case number (starting from 1) and y is the minimum number of nodes to delete from 
#G to make a full binary tree.